pub fn dp_rec_mc(amount: u32) -> u32 {
    const CASHES: [u32; 8] = [1, 2, 5, 10, 20, 30, 50, 100];
    let mut dp = vec![0; (amount + 1) as usize];
    for i in 1..=amount {
        let mut min_dp = u32::MAX;
        for &cash in CASHES.iter().rev() {
            if cash <= i {
                min_dp = min_dp.min(dp[(i - cash) as usize]);
            }
        }

        dp[i as usize] = min_dp + 1;
    }

    dp[amount as usize]
}
